perm filename TAK.BCH[TIM,LSP] blob sn#655254 filedate 1982-04-25 generic text, type C, neo UTF8
COMMENT āŠ—   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Takeuchi
C00009 ENDMK
CāŠ—;
Takeuchi
Here is the TAK benchmark plus the timings so far for the
case (TAK 18. 12. 6.) Also included are the version that GJC provided as an
additional test of FUNCALL technology. Please do at least the straight TAK
version, and possibly the TAKF version. I want to do a FUNCALL test, but
probably I want to remove arithmetic from the measurement.

Please report what your compiler does about tail recursion.

Takeuchi function of various types
tak (18. 12. 6.)

On 11/750 in Franz ordinary arith     19.9   seconds compiled
On 11/780 in Franz with (nfc)(TAKF)   15.8   seconds compiled	(GJC time)
On Dolphin in InterLisp Nov 1981 (tr) 11.195 seconds compiled
On 11/780 in Franz (nfc)	       8.4   seconds compiled	(KIM time)
On 11/780 in Franz (nfc)               8.35  seconds compiled	(GJC time)
On 11/780 in Franz with (ffc)(TAKF)    7.5   seconds compiled	(GJC time)
On 11/750 in PSL, generic arith        7.1   seconds compiled
On MC (KL) in MacLisp (TAKF)	       5.9   seconds compiled	(GJC time)
On Dolphin in InterLisp Jan 1982 (tr)  5.71  seconds compiled
On Vax 11/780 in InterLisp (load = 0)  4.24  seconds compiled
On Foonly F2 in MacLisp 	       4.1   seconds compiled
On Apollo (MC68000) PASCAL	       3.8   seconds		(extra waits?)
On 11/750 in Franz, Fixnum arith       3.6   seconds compiled
On MIT CADR in ZetaLisp		       3.16  seconds compiled	(GJC time)
On MIT CADR in ZetaLisp		       3.1   seconds compiled	(ROD time)
On MIT CADR in ZetaLisp (TAKF)         3.1   seconds compiled	(GJC time)
On Apollo (MC68000) PSL SYSLISP	       2.93  seconds compiled
On 11/780 in NIL (TAKF) 	       2.8   seconds compiled	(GJC time)
On 11/780 in NIL		       2.7   seconds compiled	(GJC time)
On 11/750 in C                         2.4   seconds
On 11/780 in Franz (ffc)	       2.13  seconds compiled	(KIM time)
On 11/780 (Diablo) in Franz (ffc)      2.1   seconds compiled	(VRP time)
On 11/780 in Franz (ffc)	       2.1   seconds compiled	(GJC time)
On 68000 in C			       1.9   second
On Utah-20 in PSL Generic arith	       1.672 seconds compiled
On 11/750 in PSL INUM arith            1.4   seconds compiled
On 11/780 (Diablo) in C  	       1.35  seconds
On 11/780 in Franz (lfc)               1.13  seconds compiled	(KIM time)
On UTAH-20 in Lisp 1.6		       1.1   seconds compiled
On UTAH-20 in PSL Inum arith	       1.077 seconds compiled
On SAIL (KL) in MacLisp	      	        .832 seconds compiled
On SAIL in bummed MacLisp           	.795 seconds compiled
On MC (KL) in MacLisp (TAKF,dcl)        .789 seconds compiled
On 68000 in machine language		.7   seconds
On MC (KL) in MacLisp (dcl)	        .677 seconds compiled
On SAIL in bummed MacLisp (dcl)	    	.616 seconds compiled
On SAIL (KL) in MacLisp	(dcl)	        .564 seconds compiled
On Dorado in InterLisp Jan 1982	(tr)	.53  seconds compiled
On UTAH-20 in SYSLISP arith		.526 seconds compiled
On SAIL in machine language		.255 seconds (wholine)
On SAIL in machine language		.184 seconds (ebox-does not include mem)
On SCORE (2060) in machine language     .162 seconds (ebox)
On S-1 Mark I in machine language       .114 seconds (ebox & ibox)

47707 function calls
max recursion depth is 18
average recursion depth is 15.4

(defun tak (x y z)
       (cond ((not (< y x))
	      z)
	     (t (tak (tak (1- x) y z)
		     (tak (1- y) z x)
		     (tak (1- z) x y))))))

notes:
(tr) means Tail Recursion Removal
(nfc) means `normal function call' in Franz (debugging setting (like (NOUUO t)))
(ffc) means `fast function call' in Franz (non-debugging setting (like (NOUUO ()))
(lfc) means `local function call' in Franz (function call directly to an entry point
					    using knowledge of the internals of the
					    function by the compiler)
(dcl) means heavy MacLisp declarations

;;; Here ar the definitions of TAKF as provided by GJC. #-NIL means
;;; except in NIL, #+NIL means for NIL.
(defun takf (x y z)
  (takfsub #'takfsub x y z))

#-NIL
(defun takfsub (f x y z)
  (if (not (< y x))
      z
      (funcall f f (funcall f f (1- x) y z)
	       (funcall f f (1- y) z x)
	       (funcall f f (1- z) x y))))

#+NIL
(defun takfsub ((&function f) x y z)
  ;; lexical scoping of function bindings allows this.
  (if (not (< y x))
      z
      (f #'f (f #'f (1- x) y z)
	 (f #'f (1- y) z x)
	 (f #'f (1- z) x y))))